package structure.linkedlist;

/**
 * 线性表的链式存储结构 单链表
 */
public class SingleList {
    // 链表节点
    static class ListNode {

        private int val;

        private ListNode next = null;

        // 构造函数
        public ListNode(int val) {
            this.val = val;
        }
    }

    // 头节点
    private ListNode head;

    // 链表的长度
    public int size() {
        int size = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }

    // 在链表尾部插入元素
    public Boolean add(int val) {
        ListNode newNode = new ListNode(val);
        if(head == null) {
            head = newNode;
            return true;
        }
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
        return true;
    }

    // 在链表中间插入元素
    public Boolean insert(int index, int val) {
        if(index < 0 || index > size()) {
            return false;
        }
        ListNode newNode = new ListNode(val);
        if(index == 0) {
            newNode.next = head;
            head = newNode;
            return true;
        }
        ListNode cur = head;
        while(--index > 0) {
            cur = cur.next;
        }
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
    }

    // 删除元素 如果链表是不可重复的，那就是删除元素，如果链表是可重复的，那么就是删除第一个 elem
    public Boolean remove(int elem) {
        if(head == null) {
            return false;
        }
        ListNode cur = head;
        while(cur.next != null) {
            if(cur.next.val == elem) {
                cur.next = cur.next.next;
            }
        }
        return true;
    }

    // 打印链表
    public void print() {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void createList(int n) {
        head = new ListNode(0);
        for(int i = 1; i < n; i++) {
            ListNode newNode = new ListNode(i);
            newNode.next = head;
            head = newNode;
        }
    }

    public void clearList() {
        if(head != null) {
            while(head != null) {
                ListNode next = head.next;
                head.next = null;
                head = next;
            }
        }
    }
}
